package zuo.algo.c04;

import zuo.algo.util.SortUtils;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 01:19-堆排序扩展题目
 * 已知一个几乎有序的数组，几乎有序是指，如果想把数组排好序，每个元素移动的距离不超过k,并且k相对于数组来说很小。
 * 选择一个合适的排序算法针对这个数据进行排序。
 */
public class SortArrDistanceLessK {

    public static void sort(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(k + 1);
        for (int i = 0; i < Math.min(arr.length, k); i++) {
            heap.add(arr[i]);
        }

        int idx = 0;
        for (int i = heap.size(); i < arr.length; i++) {
            heap.add(arr[i]);
            arr[idx++] = heap.poll();
        }

        while (!heap.isEmpty()) {
            arr[idx++] = heap.poll();
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10000000; i++) {
            int[] arr1 = getRandomArr();
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            sort(arr1, 10);
            Arrays.sort(arr2);
            SortUtils.assertArr(arr1, arr2);
            System.out.println(i);
        }
    }


    public static int[] getRandomArr() {
        Random random = new Random();
        int realLen = random.nextInt(100000) + 1;
        int[] arr = new int[realLen];
        for (int i = 0; i < realLen; i++) {
            int k = 10 * (i / 10 + 1);
            arr[i] = random.nextInt(10) + k;
        }
        return arr;
    }
}
